/**
 * 快速排序-递归代码实现
 */
public class QuickSort {
  public static void main(String[] args) {
    int[] array = new int[]{3, 5, 1, 2, 4, 8, 0};
    // 调用快排
    quickSort(array, 0, array.length - 1);
    for (int arr : array) {
      System.out.println(arr);
    }
  }

  public static void quickSort(int[] arr, int begin, int end) {
    if (end <= begin) {
      return;
    }
    int pivot = pattition(arr, begin, end);
    quickSort(arr, begin, pivot - 1);
    quickSort(arr, pivot + 1, end);
  }
  
  private static int pattition(int[] arr, int begin, int end) {
    int pivot = end, counter = begin;
    for (int i = begin; i < end; ++i) {
      if (arr[i] < arr[pivot]) {
        // 使用位运算交换两个数的值
        int tmp = arr[counter] ^ arr[i];
        arr[counter] = arr[counter] ^ tmp;
        arr[i] = arr[i] ^ tmp;
        // counter统计的是在pivot的左边，小于array[pivot]的元素的个数
        counter++;
      }
    }
    // 使用位运算交换两个数的值
    int tmp = arr[pivot] ^ arr[counter];
    arr[pivot] = arr[pivot] ^ tmp;
    arr[counter] = arr[counter] ^ tmp;
    return counter;
  }
}
